Hexer

Memory limit: 32 MB

Byteasar has become a hexer - a conqueror of monsters. Currently he is to return to his hometown Byteburg. The way home, alas, leads through a land full of beasts. Fortunately the habitants, forced to fight the monsters for centuries, have mastered the art of blacksmithery - they are now capable of making special swords that are very efficient against the beasts. The land Byteasar wanders through is quite vast: many towns lie there, and many roads connect them. These roads do not cross outside the towns (mostly because some of them are underground passages).

Byteasar has gathered all practical information about the land (all hexers like to know these things). He knows what kind of monsters he may come across each of the roads and how much time he needs to walk it down. He also knows in which villages there are blacksmiths and against what kinds of monsters the swords that they make work. Byteasar wants to get back to Byteburg as soon as possible. As a hexer he is quite ashamed that he does not know the best route, and that he has no sword on him at the moment. Help him find the shortest path to Byteburg such that whenever he could meet some king of monster, previously he would have a chance to get an appropriate sword to fight the beast. You need not worry about the number or weight of the swords - every hexer is as strong as an ox, so he can carry (virtually) unlimited number of equipment, swords in particular.

Input

The first line of the standard input holds four integers: , , and (, , , ), separated by single spaces, that denote respectively: the number of towns, the number of roads connecting them, the number of different kinds of monsters and the number of blacksmiths. The towns are numbered from to in such a way that is Byteburg's number and is the number of the village which Byteasar starts in. The monster kinds are numbered from to .

In the following lines the profiles of successive blacksmiths are given, one per line. The -st line holds the integers , , (, , ), separated by single spaces, that denote respectively: the number of town in which the blacksmith lives, the number of different kinds of monsters against which his swords are efficient, and the kinds of monsters themselves (in increasing order). Note that a town may have more than one blacksmith.

Then lines with roads' descriptions follow. The -th line holds the integers , , , , (, , , ) separated by single spaces, that denote respectively: the towns that the road connects, the time needed to walk down the road (same in both directions), the number of different kinds of monsters that may appear on that road, and finally the kinds of monsters themselves (in increasing order). No two roads connect the same pair of towns.

Output

Your programme is to print out one integer to the standard output - the minimum summary time required to reach Byteburg. Should reaching Byteburg be impossible, the number should be .

Example

For the input data:

6 7 4 2
2 1 2
3 2 1 3
1 2 2 0
2 3 9 0
1 4 2 1 2
2 5 3 0
4 5 5 2 2 3
4 6 18 0
5 6 3 2 1 2

the correct result is:

24

And for the following data set:

2 1 1 1
2 1 1
1 2 1 1 1

the correct result is:

-1

Commentary on examples

The discs in the figures represent towns; the numbers inside are the towns' numbers. The edges represent the roads; the numbers above them - the time needed to walk down the road. The numbers next to the discs (in italics) denote the kinds of monsters which the swords made the town's blacksmith(s) work against. The numbers below the edges (in italics) denote the kinds of monsters one can come across on the road.

Byteasar the hexer should first go to town no. 2, acquire a sword against the monster of kind 2, go back to town 1, then proceed to town 4 and from there finally go to Byteburg.

In the second example Byteasar is unable to acquire a sword against the monster of kind 1, which makes reaching Byteburg impossible.

Task author: Michal Wlodarczyk.